/**
 * Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7]
  [9,20],
  [3],
]
 */
package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;


public class LevelOrderButtom {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) 
    {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        HashMap<Integer, List<TreeNode>> levelMap = new HashMap<Integer, List<TreeNode>>();
        preOrder(root, levelMap, 0);
        
        List<Map.Entry<Integer, List<TreeNode>>> levelSort = 
                new ArrayList<Map.Entry<Integer, List<TreeNode>>>();
            
            levelSort.addAll(levelMap.entrySet());
            Collections.sort(levelSort, new Comparator<Map.Entry<Integer, List<TreeNode>>>(){

				@Override
				public int compare(Entry<Integer, List<TreeNode>> arg0,
						Entry<Integer, List<TreeNode>> arg1) {
					// TODO Auto-generated method stub
					int key0 = arg0.getKey();
					int key1 = arg1.getKey();
					
					return key0 > key1 ? 1 : (key0 == key1 ? 0 : -1);
				}
            	
            });
            Collections.reverse(levelSort);
         
            
        for(Map.Entry<Integer, List<TreeNode>> entry : levelSort)
        {
            List<TreeNode> nodes = entry.getValue();
            ArrayList<Integer> levelRes = new ArrayList<Integer>();
            for(TreeNode node : nodes)
            {
                levelRes.add(node.val);
            }
            result.add(levelRes);
        }
        
        return result;
            
    }
    
    public void preOrder(TreeNode root, HashMap<Integer, List<TreeNode>> levelMap, int level)
    {
        if(root == null)
            return;
            
        if(levelMap.get(level) == null)
        {
            List<TreeNode> nodeLevel = new ArrayList<TreeNode>();
            levelMap.put(level, nodeLevel);
        }
        levelMap.get(level).add(root);
        
        preOrder(root.left, levelMap, level+1);
        preOrder(root.right, levelMap, level+1);
    }
    
    class TreeNode {
   	 int val;
   	 TreeNode left;
   	 TreeNode right;
   	 TreeNode(int x) { val = x; }
   }
}
